package HOT;

/**
 * Author  zxy
 * Date  2023/6/9 下午 5:38
 */
public class NextPermutation {
    public void nextPermutation(int[] nums) {

        int len = nums.length;

        int temp;
        for (int i = len - 1; i > 0; i--) {
            if (nums[i] > nums[i - 1]) {
                int minm = Integer.MAX_VALUE;
                int index = i;
                for (int j = len - 1; j >= i; j--) {
                    if (nums[j] > nums[i - 1]) {
                        if (minm > nums[j]) {
                            minm = nums[j];
                            index = j;
                        }
                    }
                }

                temp = nums[i - 1];
                nums[i - 1] = nums[index];
                nums[index] = temp;

                // System.out.println(Arrays.toString(nums));
                // System.out.println(index);
                reverseNums(nums, i);

                return;
            }
        }

        reverseNums(nums, 0);

        return;

    }

    void reverseNums(int[] nums, int index) {
        int len = nums.length;
        int temp;
        for (int i = 0; i < (len - index) / 2; i++) {
            temp = nums[i + index];
            nums[i + index] = nums[len - 1 - i];
            nums[len - 1 - i] = temp;
        }
    }
}